1. Field of the Invention
The present invention relates to a data encoding method and apparatus and a data decoding method and apparatus and, more particularly, to a data encoding method and apparatus which encode character data having a fixed length by assigning a code length corresponding to an output frequency, and a data decoding method and apparatus which decode such encoded data.
In recent years, various types of data such as a character code, vector information and image data are handled by computers. The amount of data to be handled has been rapidly increasing. When a large amount of data is processed, a necessary memory capacity can be reduced and a high-speed data transmission can be achieve by compressing the data by eliminating a redundant part of the data.
As a method for compressing data by eliminating a redundant part of the data, a universal encoding method has been suggested. The universal encoding method is classified into a F-V encoding and a V-F encoding according to the difference of their input and output methods.
The F-V encoding converts characters or character strings having a fixed length into one having a variable length. On the other hand, the V-F encoding converts characters or character strings having a variable length into one having a fixed length. Generally, the Huffman coding is classified into the F-V encoding, and a Lempel-Ziv coding is classified into the V-F encoding.
Since the F-V encoding converts an input character into a code having a predetermined length, the code can be quickly obtained from a code table but an output of the code is slow. In the V-F encoding, since a length of a character string to be encoded is not fixed and encoding is performed by searching for the corresponding longest character string, it takes a long time to obtain a code.
As mentioned above, in either case, there is a problem in that a long time is needed to output the code. Thus, the present invention aims to attempt a high-speed encoding by increasing an output speed of the code in the F-V encoding.
2. Description of the Related Art
FIG. 1 is an illustration for explaining an operation for outputting a code in a conventional F-V encoding. FIG. 1-(A) illustrates a relationship between symbols and codes; FIG. 1-(B) illustrates a byte packing operation.
In the conventional F-V encoding, as shown in FIG. 1-(A), a 2-bit code "00" is set to a symbol "a"; a code "100" is set to a symbol "b", a code "1110" is set to a symbol "c"; a code "11110" is set to a symbol "d"; and a code "01" is set to a symbol "e". Each code is set in accordance with a probability of appearance.
Conventionally, since the code is output when an 8-bit capacity of a code buffer is filled. For example, when the symbol "a" is encoded as shown in FIG. 1-(B), the code "00" corresponding to the symbol "a" is stored in the code buffer. Then, when the symbol "b" is encoded, the code "100" corresponding to the symbol "b" is stored in the code buffer subsequent to the code "00" corresponding to the symbol "a". Thus, a code "00100" is stored in the code buffer. When the symbol "c" is encoded, a code "111" included in the code "1110" corresponding to the symbol "c" is stored in the buffer. Thus, an 8-bit code "00100111" is stored in the code buffer, and the code is output from the code buffer. Reaming code "0" of the symbol "c" is stored in the code buffer. Then, when the symbol "d" is encoded, the code "11110" corresponding to the symbol "d" is stored in the code buffer subsequent to the remaining code "0" of the symbol "c". Thus, the code stored in the code buffer becomes "011110". Then, when the symbol "e" is input, the code "01" corresponding to the symbol "e" is supplied to the code buffer, and thus an 8-bit code "01111001" is stored in the code buffer, and the code is output from the code buffer.
As mentioned above, in the conventional method, a code is byte packed in the code buffer on a single-bit basis, and the code is output from the code buffer each time when 8 bits are stored in the code buffer.
Accordingly, in the conventional F-V encoding, there is a problem in that the output of the code is delayed since the code is byte packed in the code buffer on a single-bit basis, and the code is output from the code buffer each time when 8 bits are stored in the code buffer.